# @Time    : 2020/6/24 11:03
# @Author  : T-
# @Site    : 
# @File    : 104-Maximum Depth of Binary Tree.py
# @Software: PyCharm

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # method-1: DFS递归
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

        # method-2: 迭代
        # 利用栈的思想，在DFS访问每个结点时，同时更新最大的深度
        # 从深度为1的栈开始，将当前结点弹出栈并对如子节点，每一步都更新深度
        stack = []
        if root is not None:
            stack.append((1, root))

        depth = 0
        while stack != []:
            current_depth, root = stack.pop()
            if root is not None:
                depth = max(depth, current_depth)
                stack.append((current_depth + 1, root.left))
                stack.append((current_depth + 1, root.right))

        return depth




